// leetcode 88: 合并两个有序数组
// easy 
// 输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
// 输出：[1,2,2,3,5,6]

var merge = function(nums1, m, nums2, n) {
    let len1 = m - 1 ;
    let len2 = n - 1;
    let len = m + n - 1;
    while(len2 >=0){
        if(len1<0){
            nums1[len--] = nums2[len2--];
            continue;
        }
        nums1[len--] = nums1[len1] > nums2[len2] ? nums1[len1--] : nums2[len2--];
    }
};

// leetcode 1: 两数之和
// easy 
// 输入：nums = [2,7,11,15], target = 9
// 输出：[0,1]
// 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1]
var twoSum = function(nums, target) {
    if(nums.length === 0) return [];
    let map = new Map();
    for(let i=0;i<nums.length;i++){
        let k = target - nums[i];
        if(map.has(k)){
            return [map.get(k),i];
        }
        map.set(nums[i],i);
    };
    return [];
};

// leetcode 15: 三数之和
// easy 
// 输入：nums = [-1,0,1,2,-1,-4]
// 输出：[[-1,-1,2],[-1,0,1]]
//解释：满足a+b=c=0
function twosumTarget(nums,start,target){
    let res = [];
   let lo = start, high = nums.length - 1; //特别要注意边界条件
   while(lo<high){
       let left = nums[lo],right=nums[high];
       let sum = left + right;
       if(sum<target){
           lo++;
       }else if(sum>target){
           high--;
       }else if(sum == target){
          res.push([left,right]);
          while(nums[lo] === left) lo++;
          while(nums[high] === right) high--;
       }
   }
   return res;
}
var threeSum = function(nums) {
    let res = [];
    nums.sort((a,b)=>a-b);
    for(let i=0;i<nums.length;i++){
        let tuples = twosumTarget(nums,i+1, 0 - nums[i]);
        for(let tuple of tuples ){
            res.push([...tuple,nums[i]])
        }
        while(i<nums.length-1&&nums[i] == nums[i+1]) i++;
    }
    return res;
};

//数组扁平化、去重、排序
//leetcode 349 两个数组求交集
var intersection = function(nums1, nums2) {
  return Array.from(new Set(nums1)).filter(num=> nums2.includes(num));
};
//leetcode 146 lru缓存机制

//611. 有效三角形的个数
// 输入: [2,2,3,4]
// 输出: 3
var triangleNumber = function(nums) {
    if(nums.length < 3) return 0;
    nums.sort((a,b)=>a-b);
    let count = 0;
    for(let i=nums.length-1;i>1;i--){
        let left = 0,right = i-1;
        while(left < right){
            if(nums[left]+ nums[right] > nums[i]){
                count += right - left;
                right--;
            }else {
                left++
            }
        }
    }
    return count;
 };